// Prim算法求最小生成(代价)树【适用于带权连通无向图 且 最好为边稠密图；时间复杂度为O(|V|^2)】
/*
    从某一顶点开始构建生成树；
    每次将代价最小(顶点到最小生成树距离最短)的新顶点纳入生成树，直到所有顶点都纳入为止。
*/

//注意：Prim算法 和 Dijkstra算法的区别【详见P229】
/*
    1、Prim算法用于求 带权无向图 的最小生成树；而Dijkstra算法用于求 无负权值图 的单源最短路径。
    2、两个算法都是每次选取的顶点到"某一对象"权值最低，但是这个参照"对象"不同：
        Prim算法是每次要找到相对于 "当前最小生成树" 的距离最短的顶点，然后将该顶点纳入生成树；
        而Dijkstra算法是每次要找到相对于 "源头顶点" 路径长度最短的顶点，然后将该顶点纳入已找到最短路径集合。
*/

#include "MGraph.h"
#include <cstring>
#include <iostream>

using namespace std;

int MinOfArray(int *lowCost, bool *isJoin, int size) //返回未加入最小生成树且距离生成树最近的顶点
{
    int min = MAX_WEIGHT;
    int index = 0;
    for (int i = 0; i < size; ++i)
    {
        if (!isJoin[i] && min > lowCost[i])
        {
            min = lowCost[i];
            index = i;
        }
    }
    return index;
}

int main()
{
    MGraph G;        //以邻接矩阵存储的图 【注意：在Prim算法中的图为带权无向图】
    G.DirStatue = 0; //该图为无向图
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该带权图的邻接矩阵
    cout << "please input (x y weight):\n";
    for (int x, y, weight, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y >> weight;
        AddEdge(G, x, y, weight);
    }

    //数组isJoin、lowCost、path的初始化
    bool isJoin[MaxVertexNum] = {0}; //记录每个顶点是否加入最小生成树，并初始化都为false
    int lowCost[MaxVertexNum];       //未加入的顶点加入最小生成树的最小代价,并初始化都为最大值
    for (int i = 0; i < MaxVertexNum; ++i)
        lowCost[i] = MAX_WEIGHT;
    int path[MaxVertexNum]; //用于记录最小生成树的路径，并初始化都为-1
    memset(path, -1, sizeof(path));

    cout << "please input the first vertex:\n";
    int V; //每次要加入最小生成树的顶点的索引，初始化为最小生成树的根节点
    cin >> V;
    isJoin[V] = true;
    lowCost[V] = 0;

    // Prim算法
    for (int i = 1; i < G.vexnum; ++i) //进行n-1轮处理。每一轮处理：循环遍历所有顶点，找到lowCost最低且还未加入生成树的顶点加入生成树
    {
        for (int j = 0; j < G.vexnum; ++j) //生成树中每加入一个顶点就更新一次lowCost和path
        {
            if (!isJoin[j] && G.Edge[V][j] < lowCost[j]) //【注意：这里就是和Dijkstra算法唯一的区别】若邻接于顶点i的顶点j满足还未加入生成树且edge_weight[i][j] < lowCost[j]，则更新losCost和path。(注：edge_weight[i][j]表示Vi到Vj的边的权值)
            {
                lowCost[j] = G.Edge[V][j];
                path[j] = V;
            }
        }
        V = MinOfArray(lowCost, isJoin, G.vexnum); //找到lowCost最小且还未加入最小生成树的顶点加入生成树
        isJoin[V] = true;
    }

    //测试代码
    cout << "The Minimum Spanning Tree:\n";
    for (int i = 0; i < G.vexnum; ++i)
        if (path[i] != -1)
            cout << '(' << path[i] << ',' << i << ')';
    return 0;
}